package leetcode;

public class liko378 {
    public static void main(String[] args) {
        int [][]matrix=new int [][]{{1,5,9},
                               {10,11,13},
                               {12,13,15}};
        int k=8;
        int l=matrix[0][0];
        int r=matrix[matrix.length-1][matrix.length-1];
        while(l<r){
            int mid=(r-l)/2+l;
            if(num(matrix,mid)<k){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        System.out.println(r);
    }
    static  int num(int[][] matrix,int mid){
        int i=matrix.length-1;
        int j=0,k=0;
        while(i>=0&&j<matrix.length){
            if(mid>=matrix[i][j]){
                k+=i+1;
                j++;
            }else{
                i--;
            }
        }return k;

    }
}
